
<!DOCTYPE html>
<html>
<head>
  <meta charset="utf-8">
  
  <title>存树形结构的几种表设计 | SL&#39;s Blog</title>
  <meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1">
  <meta name="description" content="。有常规几种方案：  邻接表路径枚举嵌套集闭包表">
<meta name="keywords" content="设计">
<meta property="og:type" content="article">
<meta property="og:title" content="存树形结构的几种表设计">
<meta property="og:url" content="http://caltyang.cn/2016/10/08/存树形结构的几种表设计/index.html">
<meta property="og:site_name" content="SL&#39;s Blog">
<meta property="og:description" content="。有常规几种方案：  邻接表路径枚举嵌套集闭包表">
<meta property="og:locale" content="default">
<meta property="og:image" content="http://slblogimg.oss-cn-beijing.aliyuncs.com/images/20161008/邻接表.png">
<meta property="og:image" content="http://slblogimg.oss-cn-beijing.aliyuncs.com/images/20161008/路径枚举.png">
<meta property="og:image" content="http://slblogimg.oss-cn-beijing.aliyuncs.com/images/20161008/嵌套表.png">
<meta property="og:image" content="http://slblogimg.oss-cn-beijing.aliyuncs.com/images/20161008/嵌套表树.png">
<meta property="og:image" content="http://slblogimg.oss-cn-beijing.aliyuncs.com/images/20161008/闭包表.png">
<meta property="og:image" content="http://slblogimg.oss-cn-beijing.aliyuncs.com/images/20161008/闭包表树.png">
<meta property="og:image" content="http://slblogimg.oss-cn-beijing.aliyuncs.com/images/20161008/对比.png">
<meta property="og:updated_time" content="2018-10-23T06:20:14.562Z">
<meta name="twitter:card" content="summary">
<meta name="twitter:title" content="存树形结构的几种表设计">
<meta name="twitter:description" content="。有常规几种方案：  邻接表路径枚举嵌套集闭包表">
<meta name="twitter:image" content="http://slblogimg.oss-cn-beijing.aliyuncs.com/images/20161008/邻接表.png">
  
  
    <link rel="icon" href="/favicon.png">
  
  <link rel="stylesheet" href="/css/style.css">
  <!--[if lt IE 9]><script src="//cdnjs.cloudflare.com/ajax/libs/html5shiv/3.7/html5shiv.min.js"></script><![endif]-->
  
</head>
<body>
<div id="container">
  <div id="wrap">
    <header id="header">
  <div id="banner"></div>
  <div id="header-outer" class="outer">
    <div id="header-title" class="inner">
      <h1 id="logo-wrap">
        <a href="/" id="logo">SL&#39;s Blog</a>
      </h1>
      
    </div>
    <div id="header-inner" class="inner">
      <nav id="main-nav">
        <a id="main-nav-toggle" class="nav-icon"></a>
        
          <a class="main-nav-link" href="/">Home</a>
        
          <a class="main-nav-link" href="/archives">Archives</a>
        
      </nav>
      <nav id="sub-nav">
        
        <a id="nav-search-btn" class="nav-icon" title="Search"></a>
      </nav>
      <div id="search-form-wrap">
        <form action="//www.baidu.com/baidu" method="get" accept-charset="utf-8" class="search-form">
          <input type="search" name="word" maxlength="20" class="search-form-input" placeholder="Search">
          <input type="submit" value="" class="search-form-submit">
          <input name=tn type=hidden value="bds">
          <input name=cl type=hidden value="3">
          <input name=ct type=hidden value="2097152">
          <input type="hidden" name="si" value="caltyang.cn">
        </form>
      </div>
    </div>
  </div>
</header>
    <div class="outer">
      <section id="main"><article id="post-存树形结构的几种表设计" class="article article-type-post" itemscope itemprop="blogPost">
  <div class="article-meta">
    <a href="/2016/10/08/存树形结构的几种表设计/" class="article-date">
  <time datetime="2016-10-08T06:52:25.000Z" itemprop="datePublished">2016-10-08</time>
</a>
    
  </div>
  <div class="article-inner">
    
    
      <header class="article-header">
        
  
    <h1 class="article-title" itemprop="name">
      存树形结构的几种表设计
    </h1>
  

      </header>
    
    <div class="article-entry" itemprop="articleBody">
      
        <p>。有常规几种方案：</p>
<blockquote>
<p>邻接表<br>路径枚举<br>嵌套集<br>闭包表<br><a id="more"></a></p>
</blockquote>
<h2 id="邻接表"><a href="#邻接表" class="headerlink" title="邻接表"></a>邻接表</h2><hr>
<p>。使用一个 parent_id 来指向上一级节点<br><img src="http://slblogimg.oss-cn-beijing.aliyuncs.com/images/20161008/邻接表.png" alt=""></p>
<p>。缺点：</p>
<blockquote>
<p>无法完成树操作最普通的一项：查询一个节点的所有后代<br>查询和删除节点操作相对复杂</p>
</blockquote>
<h2 id="路径枚举"><a href="#路径枚举" class="headerlink" title="路径枚举"></a>路径枚举</h2><hr>
<p>。将所有的祖先的信息联合组成一个字符串，并保存为每个节点的一个属性<br><img src="http://slblogimg.oss-cn-beijing.aliyuncs.com/images/20161008/路径枚举.png" alt=""></p>
<p>。查询时，可以使用 like，比如 1/4/6/%<br>。优点</p>
<blockquote>
<p>可以比较方便的查询到一个节点的祖先和后代，插入节点也相对简单</p>
</blockquote>
<p>。缺点</p>
<blockquote>
<p>数据库没有约束来确保路径格式的正确<br>不能保证路径中的节点确实存在<br>依赖程序的逻辑代码来维护路径的字符串，且验证字符串的正确的开销大<br>VARCHAR长度有限，所以树不能无限扩展</p>
</blockquote>
<h2 id="嵌套表"><a href="#嵌套表" class="headerlink" title="嵌套表"></a>嵌套表</h2><hr>
<p>。使用两个数字（nsleft、nsright）来编码每个节点，而不是记录其直接祖先<br>。nsleft 和 nsright 约束规则如下</p>
<blockquote>
<p>1.nsleft 的数值小于该节点的所有后代的nsleft<br>2.sright 的数值大于该节点的所有后代nsright<br>3.具体的nsleft, nsright和该节点的id并没有直接的关联</p>
</blockquote>
<p><img src="http://slblogimg.oss-cn-beijing.aliyuncs.com/images/20161008/嵌套表.png" alt=""></p>
<p>。树结构：</p>
<p><img src="http://slblogimg.oss-cn-beijing.aliyuncs.com/images/20161008/嵌套表树.png" alt=""></p>
<p>。优点</p>
<blockquote>
<p>可以方便的找到一个节点的祖先和后代、可以较方便的删除节点</p>
</blockquote>
<p>。缺点</p>
<blockquote>
<p>一些简单查询（比如找父节点）、插入移动节点会复制一些<br>逻辑理解不方便</p>
</blockquote>
<h2 id="闭包表"><a href="#闭包表" class="headerlink" title="闭包表"></a>闭包表</h2><hr>
<p>。使用额外的一张表来存储path信息<br>。记录树种所有节点的关系，不仅仅是直接父子关系（并且增加一行节点指向自身）<br>。使用空间来交换时间<br>。表结构（只有2列，可以增加 length 来保留深度信息）：<br><img src="http://slblogimg.oss-cn-beijing.aliyuncs.com/images/20161008/闭包表.png" alt=""><br>。树结构<br><img src="http://slblogimg.oss-cn-beijing.aliyuncs.com/images/20161008/闭包表树.png" alt=""></p>
<p>。注意会保存以一个节点为祖先节点的所有节点，且会保留自身到自身的引用<br>。如果在有需要查询某个节点的直接子节点时，可以通过增加一个 length 来保留在树中的深度</p>
<h2 id="对比"><a href="#对比" class="headerlink" title="对比"></a>对比</h2><hr>
<p>。表对比<br><img src="http://slblogimg.oss-cn-beijing.aliyuncs.com/images/20161008/对比.png" alt=""></p>
<p>。细节<br><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br></pre></td><td class="code"><pre><span class="line">邻接表：     最方便的设计，理解简单</span><br><span class="line">递归查询：   如果数据库支持 WITH 或者 CONNECT BY PRIOR 的递归查询，可以使用</span><br><span class="line">路径枚举：   避免了一些邻接表的缺点，但是不能保证引用的完整性</span><br><span class="line">嵌套集：     不能保证引用完整性，且理解相对复杂</span><br><span class="line">闭包表：     通过引入额外的path表，功能、性能折中</span><br></pre></td></tr></table></figure></p>
<h2 id="Reference"><a href="#Reference" class="headerlink" title="Reference"></a>Reference</h2><hr>
<p>。《SQL Anti-patterm》<br>。<a href="https://segmentfault.com/a/1190000004443840" target="_blank" rel="noopener">https://segmentfault.com/a/1190000004443840</a><br>。<a href="http://cnn237111.blog.51cto.com/2359144/1226911" target="_blank" rel="noopener">http://cnn237111.blog.51cto.com/2359144/1226911</a></p>

      
    </div>
    <footer class="article-footer">
      
        <a data-url="http://caltyang.cn/2016/10/08/存树形结构的几种表设计/" data-id="cjnlj8fbk000oh9jbaygjwkp8" class="article-share-link">Share</a>
      

      

      
  <ul class="article-tag-list"><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/设计/">设计</a></li></ul>

    </footer>
  </div>
  
    
<nav id="article-nav">
  
    <a href="/2016/12/16/使用jEnv管理JDK版本/" id="article-nav-newer" class="article-nav-link-wrap">
      <strong class="article-nav-caption">Newer</strong>
      <div class="article-nav-title">
        
          使用jEnv管理JDK版本
        
      </div>
    </a>
  
  
    <a href="/2016/09/01/SpringBoot中关闭httponly/" id="article-nav-older" class="article-nav-link-wrap">
      <strong class="article-nav-caption">Older</strong>
      <div class="article-nav-title">SpringBoot中关闭httponly</div>
    </a>
  
</nav>

  
</article>

</section>
      
      <aside id="sidebar">
  
    
  
    
  <div class="widget-wrap">
    <h3 class="widget-title">Tags</h3>
    <div class="widget">
      <ul class="tag-list"><li class="tag-list-item"><a class="tag-list-link" href="/tags/Java/">Java</a><span class="tag-list-count">7</span></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/Linux/">Linux</a><span class="tag-list-count">1</span></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/Maven/">Maven</a><span class="tag-list-count">1</span></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/OSX/">OSX</a><span class="tag-list-count">2</span></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/Spring/">Spring</a><span class="tag-list-count">1</span></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/linux/">linux</a><span class="tag-list-count">3</span></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/工具/">工具</a><span class="tag-list-count">2</span></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/数据库/">数据库</a><span class="tag-list-count">1</span></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/架构/">架构</a><span class="tag-list-count">1</span></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/网络/">网络</a><span class="tag-list-count">1</span></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/设计/">设计</a><span class="tag-list-count">1</span></li></ul>
    </div>
  </div>

  
    
  <div class="widget-wrap">
    <h3 class="widget-title">Tag Cloud</h3>
    <div class="widget tagcloud">
      <a href="/tags/Java/" style="font-size: 20px;">Java</a> <a href="/tags/Linux/" style="font-size: 10px;">Linux</a> <a href="/tags/Maven/" style="font-size: 10px;">Maven</a> <a href="/tags/OSX/" style="font-size: 13.33px;">OSX</a> <a href="/tags/Spring/" style="font-size: 10px;">Spring</a> <a href="/tags/linux/" style="font-size: 16.67px;">linux</a> <a href="/tags/工具/" style="font-size: 13.33px;">工具</a> <a href="/tags/数据库/" style="font-size: 10px;">数据库</a> <a href="/tags/架构/" style="font-size: 10px;">架构</a> <a href="/tags/网络/" style="font-size: 10px;">网络</a> <a href="/tags/设计/" style="font-size: 10px;">设计</a>
    </div>
  </div>

  
    
  <div class="widget-wrap">
    <h3 class="widget-title">Archives</h3>
    <div class="widget">
      <ul class="archive-list"><li class="archive-list-item"><a class="archive-list-link" href="/archives/2018/10/">October 2018</a><span class="archive-list-count">1</span></li><li class="archive-list-item"><a class="archive-list-link" href="/archives/2018/06/">June 2018</a><span class="archive-list-count">1</span></li><li class="archive-list-item"><a class="archive-list-link" href="/archives/2018/01/">January 2018</a><span class="archive-list-count">1</span></li><li class="archive-list-item"><a class="archive-list-link" href="/archives/2017/12/">December 2017</a><span class="archive-list-count">2</span></li><li class="archive-list-item"><a class="archive-list-link" href="/archives/2017/03/">March 2017</a><span class="archive-list-count">3</span></li><li class="archive-list-item"><a class="archive-list-link" href="/archives/2017/02/">February 2017</a><span class="archive-list-count">1</span></li><li class="archive-list-item"><a class="archive-list-link" href="/archives/2016/12/">December 2016</a><span class="archive-list-count">2</span></li><li class="archive-list-item"><a class="archive-list-link" href="/archives/2016/10/">October 2016</a><span class="archive-list-count">1</span></li><li class="archive-list-item"><a class="archive-list-link" href="/archives/2016/09/">September 2016</a><span class="archive-list-count">2</span></li><li class="archive-list-item"><a class="archive-list-link" href="/archives/2016/04/">April 2016</a><span class="archive-list-count">1</span></li><li class="archive-list-item"><a class="archive-list-link" href="/archives/2016/03/">March 2016</a><span class="archive-list-count">1</span></li><li class="archive-list-item"><a class="archive-list-link" href="/archives/2016/01/">January 2016</a><span class="archive-list-count">1</span></li><li class="archive-list-item"><a class="archive-list-link" href="/archives/2015/08/">August 2015</a><span class="archive-list-count">1</span></li><li class="archive-list-item"><a class="archive-list-link" href="/archives/2014/12/">December 2014</a><span class="archive-list-count">1</span></li><li class="archive-list-item"><a class="archive-list-link" href="/archives/2014/09/">September 2014</a><span class="archive-list-count">1</span></li><li class="archive-list-item"><a class="archive-list-link" href="/archives/2013/06/">June 2013</a><span class="archive-list-count">1</span></li></ul>
    </div>
  </div>

  
    
  <div class="widget-wrap">
    <h3 class="widget-title">Recent Posts</h3>
    <div class="widget">
      <ul>
        
          <li>
            <a href="/2018/10/23/使用SSH隧道和内网渗透访问家中服务器/">使用SSH隧道和内网渗透访问家中服务器</a>
          </li>
        
          <li>
            <a href="/2018/06/11/单例的几种写法/">单例的几种写法</a>
          </li>
        
          <li>
            <a href="/2018/01/14/记OSX中遇到的一次Finder文件灰化的问题/">记OSX中遇到的一次Finder文件灰化的问题</a>
          </li>
        
          <li>
            <a href="/2017/12/23/记一次解决CLOSE-WAIT/">记一次解决CLOSE_WAIT</a>
          </li>
        
          <li>
            <a href="/2017/12/04/用Nginx进行反向代理/">用Nginx进行反向代理</a>
          </li>
        
      </ul>
    </div>
  </div>

  
</aside>
      
    </div>
    <footer id="footer">
  
  <div class="outer">
    <div id="footer-info" class="inner">
      &copy; 2018 Shawn Liu<br>
      Powered by <a href="//hexo.io/" target="_blank">Hexo</a>
      .
      Theme by <a href="https://github.com/xiangming/landscape-plus" target="_blank">Landscape-plus</a>
    </div>
  </div>
</footer>
  </div>
  <nav id="mobile-nav">
  
    <a href="/" class="mobile-nav-link">Home</a>
  
    <a href="/archives" class="mobile-nav-link">Archives</a>
  
</nav>
  <!-- totop start -->
<div id="totop">
<a title="totop"><img src="/img/scrollup.png"/></a>
</div>

<!-- totop end -->


<!-- 百度分享 start -->

<!-- 百度分享 end -->

<script src="//cdnjs.cloudflare.com/ajax/libs/jquery/1.11.1/jquery.min.js"></script>




<script src="/js/script.js"></script>

</div>
</body>
</html>
